package com.gorkr;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author gorkr
 * @title: L51
 * @projectName my-leetcode
 * @description: N皇后问题
 * @date 2021/12/1510:41
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 */



class L51 {
    private List<List<char[]>> res = new ArrayList<>();
    private List<List<String>> resString = new ArrayList<>();


    public List<List<String>> solveNQueens(int n) {
        // 初始化map

        List<char[]> map = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            char[] tmp = new char[n];
            for (int j = 0; j < n; j++) {
                tmp[j] = '.';
            }
            map.add(tmp);
        }



        backtrack(map,0);


        System.out.println(resString);

        return resString;
    }
    void backtrack(List<char[]> map, int row){
        ArrayList<String> strings = new ArrayList<>();
        if(row== map.size()){
            for (char[] c:
             map
            ) {
               strings.add(new String(c));
            }


            resString.add(strings);
            return;
        }

        for (int i = 0; i < map.size(); i++) {
            if(!isValid(map,row,i)){
               continue;
            }
            map.get(row)[i] = 'Q';
            backtrack(map, row+1);
            map.get(row)[i] = '.';
        }
    }

    private boolean isValid(List<char[]> map, int row, int col){
        //列
        for (int i = 0; i <= row; i++) {
            if(map.get(i)[col] == 'Q'){
                return false;
            }
        }

        for(int i=row-1, j=col+1; i>=0&&j<map.size();i--,j++){
            if(map.get(i)[j]=='Q'){
                return false;
            }
        }

        for(int i=row-1, j=col-1; i>=0&&j>=0; i--,j--){
            if(map.get(i)[j]=='Q'){
                return false;
            }
        }

        return true;
    }


    @Test
    public void test(){
        solveNQueens(4);
    }
}